﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace BitcoinLibrary
{
    /**
     * A custom form of base58 is used to encode BitCoin addresses. Note that this is not the same base58 as used by
     * Flickr, which you may see reference to around the internet.<p>
     *
     * Satoshi says: why base-58 instead of standard base-64 encoding?<p>
     *
     * <ul>
     * <li>Don't want 0OIl characters that look the same in some fonts and
     *    could be used to create visually identical looking account numbers.</li>
     * <li>A string with non-alphanumeric characters is not as easily accepted as an account number.</li>
     * <li>E-mail usually won't line-break if there's no punctuation to break at.</li>
     * <li>Doubleclicking selects the whole number as one word if it's all alphanumeric.</li>
     * </ul>
     */
    public class Base58
    {
        private static readonly string ALPHABET = "123456789ABCDEFGHJKLMNPQRSTUVWXYZabcdefghijkmnopqrstuvwxyz";
        private static readonly BigInteger BASE = 58;

        public static string encode(byte[] input)   // TODO: replace with BigInteger member?
        {
            // TODO: This could be a lot more efficient.
            BigInteger bi = new BigInteger(input);  // TODO: correct?
            StringBuilder s = new StringBuilder();
            while (bi.CompareTo(BASE) >= 0)
            {
                BigInteger mod = bi % BASE;
                s.Insert(0, ALPHABET[(int)mod]);
                bi = (bi - mod) / BASE;
            }
            s.Insert(0, ALPHABET[(int)bi]);
            // Convert leading zeros too.
            foreach (byte anInput in input)
            {
                if (anInput == 0)
                    s.Insert(0, ALPHABET[0]);
                else
                    break;
            }
            return s.ToString();
        }

        public static byte[] decode(string input)   // TODO: replace with BigInteger member?
        {
            byte[] bytes = decodeToBigInteger(input).ToByteArray();
            // We may have got one more byte than we wanted, if the high bit of the next-to-last byte was not zero. This
            // is because BigIntegers are represented with twos-compliment notation, thus if the high bit of the last
            // byte happens to be 1 another 8 zero bits will be added to ensure the number parses as positive. Detect
            // that case here and chop it off.
            bool stripSignByte = bytes.Length > 1 && bytes[0] == 0 && bytes[1] < 0;
            // Count the leading zeros, if any.
            int leadingZeros = 0;
            for (int i = 0; input[i] == ALPHABET[0]; i++)
            {
                leadingZeros++;
            }
            // Now cut/pad correctly. Java 6 has a convenience for this, but Android can't use it.
            byte[] tmp = new byte[bytes.Length - (stripSignByte ? 1 : 0) + leadingZeros];
            Array.Copy(bytes, stripSignByte ? 1 : 0, tmp, leadingZeros, tmp.Length - leadingZeros);
            return tmp;
        }

        public static BigInteger decodeToBigInteger(string input) // TODO: replace with BigInteger member?
        {
            BigInteger bi = 0;
            // Work backwards through the string.
            for (int i = input.Length - 1; i >= 0; i--)
            {
                int alphaIndex = ALPHABET[input[i]];
                if (alphaIndex == -1)
                {
                    throw new Exception("Illegal character " + input[i] + " at " + i);
                }
                bi = bi + (new BigInteger(alphaIndex) * BigInteger.Pow(BASE, input.Length - 1 - i));    // TODO: correct?
            }
            return bi;
        }

        /**
         * Uses the checksum in the last 4 bytes of the decoded data to verify the rest are correct. The checksum is
         * removed from the returned data.
         *
         * @throws AddressFormatException if the input is not base 58 or the checksum does not validate.
         */
        public static byte[] decodeChecked(string input)
        {
            byte[] tmp = decode(input);
            if (tmp.Length < 4)
            {
                throw new Exception("Input too short");
            }
            byte[] checksum = new byte[4];
            Array.Copy(tmp, tmp.Length - 4, checksum, 0, 4);
            byte[] bytes = new byte[tmp.Length - 4];
            Array.Copy(tmp, 0, bytes, 0, tmp.Length - 4);
            tmp = Utils.doubleDigest(bytes);
            byte[] hash = new byte[4];
            Array.Copy(tmp, 0, hash, 0, 4);
            if (!Array.Equals(hash, checksum))
            {
                throw new Exception("Checksum does not validate");
            }
            return bytes;
        }
    }
}